package com.zhupf.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhupf
 * @date 2023年12月26日 15:21
 * @Description
 *
 * 17. 电话号码的字母组合
 */
public class LetterCombinations {

    static char[][] numbers = {
            {}, {}, {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
            {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}
    };

    private static List<String> ans = new ArrayList<>();

    public static void main(String[] args) {
        letterCombinations("23");
    }

    public static List<String> letterCombinations(String digits) {
        StringBuilder res = new StringBuilder();
        if(digits == null || digits.length() == 0){
            return ans;
        }
        int len = digits.length();
        dfs(len,res,digits,0);
        return ans;
    }

    private static void dfs(int len,StringBuilder res,String digits,int idx){
        if(res.length() == len){
            ans.add(res.toString());
            return;
        }
        char[] number = numbers[digits.charAt(idx)-'0'];
        for (int i = 0; i < number.length; i++) {
            res.append(number[i]);
            dfs(len,res,digits,idx+1);
            res.deleteCharAt(res.length()-1);
        }
    }

}
